import collections
class LockingTree(object):

    def __init__(self, parent):
        """
        :type parent: List[int]
        """
        self.child = collections.defaultdict(set)
        for ch, p in enumerate(parent):
            if p != -1:
                self.child[p].add(ch)
        self.n = len(parent)
        self.parent = parent
        self.d = {i:0 for i in range(self.n)}

    def lock(self, num, user):
        """
        :type num: int
        :type user: int
        :rtype: bool
        """
        if not self.d[num]:
            self.d[num] = user
            return True
        else:
            return False


    def unlock(self, num, user):
        """
        :type num: int
        :type user: int
        :rtype: bool
        """
        if self.d[num] == user:
            self.d[num] = 0
            return True
        else:
            return False

    def dfs(self, num):
        out = []
        if self.d[num]:
            out.append(num)
        for ch in self.child[num]:
            out += self.dfs(ch)
        return out


    def upgrade(self, num, user):
        """
        :type num: int
        :type user: int
        :rtype: bool
        """
        if not self.d[num]:
            node = num
            while node != -1:
                if self.d[node]:
                    return False
                else:
                    node = self.parent[node]
            out = self.dfs(num)
            if out:
                self.d[num] = user
                for ch in out:
                    self.d[ch] = 0
                return True
            else:
                return False
        else:
            return False

